#include <iostream>
#include <string>
#include <vector>

using namespace std;



class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        // 初始化
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++){
            if (p[i - 1] == '*') dp[0][i] = 1;
            else break;
        }
        for (int i = 1; i <= n; i++){

            for (int j = 1; j <= m; j++){
                if (p[j-1] == '?' || s[i-1] == p[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                /*
                // 1.  dp[i][j-1] 匹配 0 个字符； 2. dp[i-1][j]表示匹配 1~N个 字符；
                匹配 1~N 个字符这里或许可以这么理解：因为 *匹配 1 ~N个，匹配一个的话就是dp[i-1][j-1]，但是这是不对的，忽略了*号可以匹配N个的机制，
                所以表示下标 i 的那一个维度减 1 ，意思就是不仅不匹配了s[i-1]，还可以继续多匹配字符。因为这么一想：不就是*号不仅可以匹配掉当前对应的s[i-1]，还可以继续使用来匹配更前面s[i-2]的意思吗？？
                
                */
                else if (p[j-1] == '*'){
                    dp[i][j] = dp[i][j-1] | dp[i-1][j] ; 
                }
            }
        }

        return bool(dp[n][m]);
    }
};